As data is transferred through a data processing machine, errors occur due to failures of memory devices or electrical contacts or other reasons. Thus, data processing machines have mechanisms for detecting errors that occur as the data is moved from one point to another within the machine.
A common method for detecting errors which is often implemented is accomplished by calculating the parity of each byte of data as it is moved between portions of the data processing machine. This method is simple to implement and can be used throughout the data processing machine. It does add one bit to the length of storage required for each byte over which parity is generated. The error checking is done by first calculating the parity of the data byte in question, then transferring the data to the portion of the data processing machine desired, and last, regenerating the parity at the location to which the data is transferred and comparing that regenerated parity with the earlier parity. If the parity bits do not coincide, then an error has occurred within the byte. The parity is generated by simply taking the exclusive-OR of the bits within the byte.
Although parity checking is a simple and economical means for detecting errors that may occur within a byte, it is limited in that it can only detect errors if they occur to odd numbers of bits with the byte, and it does not indicate to which bit within the byte the error occurred. Thus, even though a parity check will indicate that the data contains an error it will not enable the data processing machine to correct that error.
The reliability of a data processing machine can be enhanced to a large degree by including a mechanism for correcting errors that are detected. Thus typically, data processing machines include logic between major portions of the machines, such as between the various memory arrays, by which errors can be detected and corrected.
Data processing machines typically move data from one storage facility to another or from one storage facility to the execution unit in words of a number of bytes of data. An acceptable design parameter for implementing error checking and correcting mechanisms is to correct all single bit errors that occur in those words of data and further to detect any double bit errors that occur. For a data word of 64 bits long which is divided into eight bytes of eight bits each, the minimum storage required to resolve the error detecting and correcting with a Hamming code function which will accomplish the single bit correction and double bit detection parameter is eight bits for each data word.
The error detecting and correcting mechanism is a rather complicated mechanism as compared to the parity mechanism, so it is not implemented every time the data transfers from one portion of the machine to another. On the other hand, the parity checking is simple enough to be implemented throughout a machine and is commonly so implemented. The amount of storage needed for error detection and correction is determined by the size of the block of data over which the detection and correction is to be accomplished and the capabilities of the error detection and correction desired. Further, error detecting and correcting is normally implemented over larger blocks of data than simple parity checking. Therefore, parity is used for checking over blocks of data of a size which is transferred from unit to unit in the data processing machine more often than over the larger error detection and correction block.
Thus each byte of data that is being transferred through the data processing machine commonly includes a parity bit. Thus, as the data is transferred into a storage facility, an additional bit of storage is included for the parity bit. In our example of a 64 bit word with eight eight-bit bytes, the storage required per byte would be nine bits in order to preserve the parity bit. With the addition of an eight-bit Hamming code that would be necessary to resolve single bit error correction and double bit error detection, the total storage required for the 64 bit word will be 64 bits of data plus eight parity bits plus eight bits for the Hamming code.
Storage in data processing machines is expensive, especially when a specialized storage facility such as those that are designed for fast access of data is involved.
Thus there is a need for an apparatus for reducing the storage necessary for error correction and detection in a data processing machine.